package main

import "fmt"

func main() {
	arr := []int{16, 15, 12, 5, 9, 7, 6, 2, 1}
	//insertSort(arr)
	//selectSort(arr)
	//maopao(arr)
	shellSort(arr, 9)
}
func shellSort(arr []int, n int) {
	var j int
	for inc := n / 2; inc > 0; inc /= 2 {
		for i := inc; i < n; i++ {
			key := arr[i]
			for j = i; j >= inc && key < arr[j-inc]; j -= inc {
				arr[j] = arr[j-inc]
			}
			arr[j] = key
		}
	}
	fmt.Println(arr)
}

func maopao(arr []int) {

	for i := len(arr) - 1; i > 0; i-- {
		for j := 0; j < i; j++ {
			if arr[j] > arr[j+1] {
				arr[j], arr[j+1] = arr[j+1], arr[j]
			}
		}
	}
	fmt.Println(arr)
}
func selectSort(arr []int) {
	var i, j int
	for i = 0; i < len(arr); i++ {
		min := i
		for j = i + 1; j < len(arr); j++ {
			if arr[min] > arr[j] {
				min = j
			}
		}
		arr[i], arr[min] = arr[min], arr[i]
	}
	fmt.Println(arr)
}
func insertSort(arr []int) {
	for i := 1; i < len(arr); i++ {
		tmp := arr[i]
		index := i - 1
		for index >= 0 && arr[index] > tmp {
			arr[index+1] = arr[index]
			index--
		}
		arr[index+1] = tmp
		fmt.Println("i= ", i)
		fmt.Println(arr)
	}

	fmt.Println(arr)
}
